package leetcode.solution;

/**
 * 给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。
 *
 * 学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。
 *
 * 学生必须坐在状况良好的座位上。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：seats = [["#",".","#","#",".","#"],
 *               [".","#","#","#","#","."],
 *               ["#",".","#","#",".","#"]]
 * 输出：4
 * 解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。
 * 示例 2：
 *
 * 输入：seats = [[".","#"],
 *               ["#","#"],
 *               ["#","."],
 *               ["#","#"],
 *               [".","#"]]
 * 输出：3
 * 解释：让所有学生坐在可用的座位上。
 * 示例 3：
 *
 * 输入：seats = [["#",".",".",".","#"],
 *               [".","#",".","#","."],
 *               [".",".","#",".","."],
 *               [".","#",".","#","."],
 *               ["#",".",".",".","#"]]
 * 输出：10
 * 解释：让学生坐在第 1、3 和 5 列的可用座位上。
 *  
 *
 * 提示：
 *
 * seats 只包含字符 '.' 和'#'
 * m == seats.length
 * n == seats[i].length
 * 1 <= m <= 8
 * 1 <= n <= 8
 * 通过次数1,561提交次数3,618
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-students-taking-exam
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class difficult_参加考试的最大学生数 {
    class Solution {
        private int ok(char[][] grid, int x, int m, int cur) {
            int cnt = 0;//检查合理性 同时进行1的计数
            for (int i = 0; i < m; i++) {
                int a = x & (1 << i);
                if (a != 0) cnt++;
                if (grid[cur][i] == '#' && (a) != 0)//坏的位置不能有人
                    return -1;
                if (i > 0) {
                    int b = x & (1 << (i - 1));//一行中连续的位置不能同时有人
                    if (a != 0 && b != 0) return -1;
                }
            }
            return cnt;
        }

        /**
         *
         * 状态转移方程为dp[i][j]=max(dp[i][j],dp[i-1][k]+cnt)
         * 对于本题来讲，通过分析，我们也可以表示类似的状态，dp[i][j] 表示当第 i 行的座位分布为 j 时，前 i 行可容纳的最大学生人数。
         * j 是 000100 的整数表出
         */
        public int maxStudents(char[][] seats) {
            int n = seats.length;
            if (n == 0) return 0;
            int m = seats[0].length;
            int[][] grid = new int[n][m];
            int total = 1 << m;
            int[][] dp = new int[n + 1][total + 1];
            int res = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < total; j++) {
                    int one = ok(seats, j, m, i - 1);
                    if (one == -1) continue;
                    for (int k = 0; k < total; k++) {
                        //枚举上一个状态，通过左移和右移来判断左前和右前是否冲突
                        if (((j << 1) & k) != 0 || ((j >> 1) & k) != 0) continue;
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + one);
                        res = Math.max(dp[i][j], res);
                    }
                }
            }
            return res;
        }
    }
}
